package com.dq.node;

/**
 * @author DQ
 * @version 1.0
 * @date 2021/1/8 18:29
 */
public class List {
    private ListNode head;
    public List(int n){
        this.head = List.newList(n);
    }
    public List(int[] a){
        this.head = List.newList(a);
    }
    public void show(){
        List.showList(this.head);
    }
    //产生长度为N的链表
    public static ListNode newList(int n){
        int[] list = new int[n];
        for (int i = 0; i < list.length; i++) {
            list[i] = (int) (Math.random()*100);
        }
        return newList(list);
    }
    //根据list产生链表
    public static ListNode newList(int ...list){
        ListNode head = new ListNode(0);
        ListNode temp = head;
        for (int i = 0; i < list.length; i++) {
            temp.next = new ListNode(list[i]);
            temp = temp.next;
        }
        return head.next;
    }


    //打印链表
    public static void showList(ListNode head){
        if (head==null) {
            System.out.println("链表为空！");
        }
        StringBuilder res = new StringBuilder("");
        res.append(head.val);
        while(head.next!=null){
            res.append(" -> " + head.next.val);
            head = head.next;
        }
        System.out.println(res);
    }

    // 反转链表，递归
    public static ListNode reverseList(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode last = reverseList(head.next);
        //反转
        head.next.next = head;
        head.next = null;
        return last;
    }
    // 反转链表的前N个，递归
    public static ListNode reverseListN(ListNode head, int n){
        if(n==1||head.next==null) return head;
        ListNode last = reverseListN(head.next, n-1);
        //记录下 之后 开头要连接的地方
        ListNode successor = head.next.next;
        head.next.next = head;
        head.next = successor;
        return last;
    }
    // 反转链表的m-n个，方法一，递归
    public static ListNode reverseListMN(ListNode head, int m,int n){
        if(n==1||head.next==null) return head;
        ListNode last = reverseListMN(head.next, m-1, n-1);
        if (m<=1){
            ListNode successor = head.next.next;
            head.next.next = head;
            head.next = successor;
        return last;
    }
        head.next = last;
        return head;
    }
    // 反转链表的m-n个，方法二，递归
    public static ListNode reverseListMN2(ListNode head, int m,int n){
        if(m==1){
            return reverseListN(head, n);
        }
        if(head.next==null) return head;
        head.next = reverseListMN2(head.next,m-1, n-1);

        return head;
    }
    // 反转链表，循环
    public static ListNode reverseListIter(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode first = head;
        ListNode second = head.next;
        while(second!=null){
            ListNode temp = second.next;
            second.next = first;
            first = second;
            second = temp;
        }

        head.next = null;
        return first;
    }
    // 反转链表的前N个，循环
    public static ListNode reverseListNIter(ListNode head, int n){
        if(head==null||head.next==null) return head;
        ListNode first = head;
        ListNode second = head.next;
        while(--n>=1 && second!=null){

            ListNode temp = second.next;
            second.next = first;
            first = second;
            second = temp;
        }
        head.next = second;
        return first;
    }
    // 反转链表的m-n个，循环
    public static ListNode reverseListMNIter(ListNode head, int m,int n){
        if(head==null||head.next==null) return head;
        ListNode last = head;
        //以m开头节点为第几个
        if(m==1){
            return reverseListNIter(head,n);
        }
        n = n-m+1;
        while(--m>1) last = last.next;
        last.next = reverseListNIter(last.next,n);
        return head;

    }

    public static void main(String[] args) {
        ListNode head = List.newList(new int[]{1,2,3,4,5,6,7,8,9});
        List.showList(head);
        head = List.reverseListNIter(head,2);
        List.showList(head);
    }
}
